This invention relates to methods of doing “ASIC-aware” technology mapping for FPGAs or the like. For example, these are methods whereby the logic module or logic element outputs of the FPGA version of a user's logic design are also made “visible” in a structured ASIC version of the design.
A field programmable logic device (“FPGA”) typically includes a network of logic elements (“LEs”). Each LE typically contains an N-input look-up table (“LUT”) that can select the logical output of one of 2N configuration RAM bits (“CRAM bits”). By programming these bits appropriately, the LUT can be programmed to implement any logical function of N-inputs. The FPGA also contains programmable routing resources for connecting the inputs and outputs of LEs. Routing resources typically include routing muxes that are controlled by configuration bits. Thus, an FPGA has great flexibility, in that it can implement many different logic circuits simply by programming the configuration bits. However, a significant amount of the die area—and hence the device cost—comes from the circuitry needed to make the device configurable, e.g., the CRAM bits, the LUT circuitry, and the routing multiplexer circuitry.
A structured gate array is a mask-programmable logic device. Typically, it includes a uniform structure of “hard” logic elements (“HLEs”). These HLEs are typically multi-gate circuits that are much smaller than the programmable LEs of FPGAs, and implement simpler functions. These HLEs may be combined to form units called clusters of HLEs (“CHLEs”). An HLE is typically capable of implementing only some very simple two- or three-input functions, while a CHLE can implement functions of similar complexity to an N-input LUT. However, unlike a LUT, a CHLE with M inputs may be able to implement only a subset of all possible 2M functions of those M inputs.
The inputs and outputs of CHLEs are connected together via metal wires defined by one or more custom routing mask layers. Here, “mask” refers to the lithographic mask used in the integrated circuit manufacturing process. Some of the custom mask layers may also affect the functionality of the CHLE itself, by making connections within the HLE (and controlling, e.g., whether the HLE implements an AND or OR gate).
A structured gate array is not field-programmable. Once a custom mask has been made and once a device has been fabricated using this custom mask, the logic implemented in the device is fixed. Such a device is called an application-specific integrated circuit (“ASIC”) or, in this case, a “structured ASIC” because at least the rudiments of an array of HLEs are always present (in addition to the customized features provided by the custom mask layers). An ASIC is much smaller than an equivalent FPGA, but the custom mask layers can result in high non-recoverable engineering costs (“NREs”). Once manufactured, it is not possible to fix mistakes in an ASIC without again incurring these NRE costs.
Technology mapping refers to the steps by which a design engineering automation (“EDA”) software tool converts a user's specification of a design into a netlist of logic elements. Typically, the user's representation of a design is specified as a network of logic gates (e.g., AND gates, OR gates, and register primitives). In the prior art, technology mapping to LEs (for FPGAs) and technology mapping to CHLEs (for structured ASICs) have used different methods. In the case of FPGAs, the algorithms typically included partitioning the user's netlist into cones of logic with N or fewer inputs (since a LUT can implement any function with N or fewer inputs). This is typically implemented using well-known algorithms for finding min-cuts in a graph. In the case ASICs, the algorithm is implemented using a predefined library of logical functions, each of which has a predefined mapping into a small network of one or more HLEs. Both methods then typically use these algorithm implementations inside a bottom-up greedy or dynamic programming algorithm that chooses the best cut or best HLE for each node in the user's netlist. The output netlist includes the LUTs corresponding to the best cut of each visible node, or the best HLE for each visible node (where a visible node is a node that feeds an output pin, or is any input to a LUT or HLE of another visible node). Both methods attempt to minimize an overall metric for the user's design, which is typically a combination of cost and netlist delay. The cost of a LUT is typically fixed, while the cost of a CHLE depends upon the number of HLEs it contains. Secondary cost metrics may also take into account such things as the total number of inputs to the LUT (e.g., in an attempt to minimize routing costs), or the exact library primitive chosen for the CHLE (e.g., some multi-HLE CHLE primitives may have better packing or routing characteristics).
It would be desirable for a programmable logic manufacturer to be able to offer both an FPGA and an equivalent structured ASIC device to its customers. This would allow customers to initially design for the FPGA device without incurring any NRE costs, but also, after their design is fully debugged and production has ramped up, to switch to the ASIC device to reduce their unit-device costs.
In order to make the conversion of a design from an FPGA to an ASIC as seamless as possible, it would be desirable to make the network of LEs and the network of CHLEs be as similar as possible. In particular, it would be desirable to have the visible nodes of the LE netlist also be visible in the CHLE netlist, and vice-versa, so that nodes with the same name and implementing the same functionality exist in both devices. This would simplify functional and timing verification between the two netlists. These verification steps are important to catch errors (which could occur in the FPGA to ASIC conversion) before incurring the large NRE cost due to mask and device manufacturing. The timing verification is particularly important, because the FPGA and ASIC devices will have different timing characteristics (with the internal delays of the ASIC typically being much less than those in the FPGA).
What is desired is an ASIC-aware technology mapper for an FPGA device, which takes the costs and visible nodes of both types of networks into account simultaneously.